Field
Embodiments of the present disclosure are generally directed to hash tables, and more specifically to accessing hash tables using parallel processors.
Background Art
Hash tables are data structures that store elements. To store, manipulate and retrieve elements (i.e., operations that must be supported in any dynamic set data structure), hash tables utilize operations such as insert, search and delete.
In conventional hash tables, element manipulation is efficient when performed on sequential processors, such as conventional control processing units (“CPUs”), but is inefficient when performed on parallelized processors, such as general purpose graphics processing units (“GPGPUs”). The inefficiency stems from a lack of parallelism in hash table operations, and from branch and memory divergence associated with the element storage.
In a GPGPU, multiple threads may be combined into groups provided the threads in a group execute the same set of instructions as the other threads in the group in parallel. When threads receive key look-up instructions to look up elements in a hash table, threads access the hash table in parallel to look-up keys associated with each element. However, because each key is different, the associated element of the hash table is located at a different depth in the hash table. This causes each thread to complete its key look-up at a different time. Because such threads in a group execute the same set of instructions, the threads that have successfully completed the key look-up instruction continue to execute false look-up instructions (the effects of which are “masked” and are prevented from being made permanent) as they wait for the remaining threads to complete. This leads to branch divergence and reduced thread efficiency on a parallel processor.
Therefore, what is needed is a hash table that enhances parallelism and reduces branch and memory divergence for operations on dynamic-set data structures processed by a GPGPU.